package com.wwlwxg.dataStructure;

import cn.hutool.json.JSONUtil;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.io.File;
import java.util.*;

/**
 * 目录树实现
 * 查找支持中间路径匹配
 * thought：
 * 为了简化数据结构，没有使用过多的标志，例如isRoot, isDirectory, isFile,
 * 主要数据结构为Tree，根节点数据为"", 为标识数据，不可使用。Tree内部包含一个父节点引用，一个字节点列表，一个数据项（存储路径的一个分节）
 * 只有根节点的data为"", 这个也是用来判断是否到根节点的判断依据
 *
 * Parent -->  Node  -->  ChildrenList
 * 构建树：
 *    来一个路径，会根据File.separator来分节，如果所得数据第一个元素是"",则说明是linux平台的绝对路径，将""还原为File.separator,
 * 然后一级一级的往树里面去添加，如果跟树节点data匹配，则到下一级，如果不匹配，则创建一个节点加入树中
 *
 * 查询树：
 *    来一个关键字，会从树的跟节点的儿子们开始查找，如果树中某一个节点的data包含了关键字，那么加入到匹配列表中
 *    遍历匹配列表中的没一个节点，
 *    步骤如下 ：
 *       1. 构建路径前缀： 因为很大可能匹配到的是路径的中间部分，所以通过parent属性，向上一直找到路径的根，得到了匹配路径的prefix
 *       2. 构建路径后缀： 通过children属性，遍历children的所有路径，并且拼接，得到一个列表
 *       3. 路径前缀和路径后缀，一对多的组装
 *       4. 得到路径列表
 */
public class DirectoryTree {

	Logger logger = LoggerFactory.getLogger(getClass());

	/**
	 * 内部根节点
	 */
	private Tree root = new Tree();

	public Tree getRoot() {
		return root;
	}

	public static void main(String[] args) {
		DirectoryTree directoryTree = new DirectoryTree();
		directoryTree.add("/c:"+ File.separator + "at" + File.separator + "dd.pdf");
//		directoryTree.add("/c:"+ File.separator + "tt" + File.separator + "dd" + File.separator + "ee.pdf");
//		directoryTree.add("/c:"+ File.separator + "tt" + File.separator + "dd" + File.separator + "aa.pdf");
		directoryTree.add("c:"+ File.separator + "tt" + File.separator + "dd" + File.separator + "aa.pdf");
		System.out.println(JSONUtil.toJsonStr(directoryTree));
		System.out.println();
		System.out.println(directoryTree.getFilePaths("a"));
	}

	class Tree {

		public List<Tree> children = new ArrayList<>();

		public transient Tree parent;

		public String data = "";

		public Tree() {
		}

		public Tree(String data) {
			this.data = data;
		}

		public boolean add(Tree tree) {
			children.add(tree);
			tree.parent = this;
			return true;
		}

		@Override
		public String toString() {
			return "Tree{" +
					"children=" + children +
					", data='" + data + '\'' +
					'}';
		}
	}

	/**
	 * 添加元素
	 * @param path
	 * @return
	 */
	public boolean add(String path) {

		if(Objects.isNull(path)) {
			return false;
		}

		String[] ps = path.split(File.separator);
		if("".equals(ps[0])) {
			ps[0] = File.separator;
		}
		return insert(ps, 0, root);
	}

	/**
	 * 根据关键字查询满足条件的路径
	 * @param key
	 * @return
	 */
	public List<String> getFilePaths(String key) {
		if(key == null) {
			logger.warn("keys is null...");
			throw new RuntimeException("keys is null...");
		}

		List<String> pathList = new ArrayList<>();

		final Tree tree = root;
		List<Tree> list = new ArrayList<>();
		search(tree, key, list);
		for(Tree t : list) {
			pathList.addAll(constructFilePaths(t));
		}

		return pathList;
	}

	/**
	 * 返回匹配的文件路径列表
	 *
	 * @return
	 */
	private List<String> constructFilePaths(Tree tree) {
		Tree treeTmp = tree;
		String prefix = treeTmp.data;

		Tree parent = treeTmp.parent;
		while(!parent.data.equals("")) {
			if(parent.data.equals(File.separator)) {
				prefix = File.separator + prefix;
			} else {
				prefix = parent.data + File.separator + prefix;
			}
			parent = parent.parent;
		}
		// 获取所有的children路径list
		List<String> pathList = new ArrayList<>();
		constructChildren(tree, prefix, pathList);

		return pathList;
	}

	/**
	 *
	 * @param tree
	 * @param prefix
	 * @param result: 路径列表
	 * @return
	 */
	private void constructChildren(Tree tree,String prefix, List<String> result) {

		List<Tree> children = tree.children;
		for(Tree t : children) {
			constructChildren(t, prefix + File.separator + t.data, result);
		}
		if(children.size() == 0) {
			result.add(prefix);
		}
	}

	/**
	 * TODO
	 * @param tree
	 * @param key
	 */
	private void search(Tree tree, String key, List<Tree> result) {
		if(tree == null) {
			return;
		}
		String data = tree.data;
		if(data.contains(key)) {
			result.add(tree);
		} else {
			for(Tree t : tree.children) {
				search(t, key, result);
			}
		}
	}

	private boolean insert(String[] ps, int index, Tree root) {

		if(index == ps.length) {
			return true;
		}

		List<Tree> children = root.children;
		String data = ps[index];

		for(Tree tree : children) {
			String treeData = tree.data;
			if(data.equals(treeData)) {
				index++;
				return insert(ps, index, tree);
			}
		}

		if(index < ps.length) {
			Tree tree = new Tree();
			tree.data = ps[index];
			root.add(tree);
			index++;
			return insert(ps, index, tree);
		}
		return true;
	}

	@Override
	public String toString() {
		return "DirectoryTree{" +
				"root=" + root +
				'}';
	}
}
